/*
 * RouteScannerBW.java
 *
 * Created on April 9, 2007, 9:42 PM
 *
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.fpdev.core.algo.path;

import org.fpdev.core.transit.SubRoute;
import org.fpdev.core.transit.Timetable;
import org.fpdev.core.routenet.RouteNetwork;
import org.fpdev.core.routenet.RNode;
import org.fpdev.core.routenet.RLink;
import org.fpdev.core.transit.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;
import org.fpdev.util.FPUtil;

/**
 * The subclass of RouteScanner for searching "backwards" through the 
 * RouteNetwork (i.e. "arrive-by" searches).
 * 
 * @author demory
 */
public class RouteScannerBW extends RouteScanner {

  private List<Integer> startTimes_;

  /** Creates a new instance of RouteScannerBW */
  public RouteScannerBW(RouteNetwork rteNet, Set<String> validSubs, RNode origin, RNode dest, int time, CalendarService service, double walkSpeedFPS) {
    super(rteNet, validSubs, origin, dest, time, service, walkSpeedFPS);
  //System.out.println("in RSBW constructor, time_="+CUtil.dtime(time_));
  }

  protected int getFinalLinkType() {
    return RLink.RLINK_BOARD;
  }

  protected Iterator<RLink> getPotentialFinalLinks() {
    return rteNet_.outLinks(origin_);
  }

  protected RNode startScanNode() {
    return dest_;
  }

  protected RNode nodeEncounteredFirst(RLink link) {
    return rteNet_.toNode(link);
  }

  protected int getType() {
    return BW;
  }

  protected int getStartTime(int i) {
    return startTimes_.get(i).intValue();
  }

  protected void initPass() {
    startTimes_ = new LinkedList<Integer>();
  }

  protected void addToSet(RNode rNode, int time) {
    //if(time<0) System.out.println("aTS time negative!!");
    Iterator<RLink> links = rteNet_.inLinks(rNode);
    //if(rNode.getID().equals("s_5P")) System.out.println("At 5P, time="+CUtil.sTimeToStr(time));

    if (finalLinks_.containsKey(rNode)) {
      Iterator<RLink> flinks = finalLinks_.get(rNode).iterator();
      while (flinks.hasNext()) {
        RLink fLink = flinks.next();
        foundPotential(new LinkedList<RLink>(), fLink, time - fLink.timeCostBW(time, service_, walkSpeedFPS_, 0));
      }
    }
    while (links.hasNext()) {
      RLink link = links.next();
      SubRoute sub = link.getSubRoute();
      if (!validSubs_.contains(sub.getMasterID())) {
        continue;
      }

      int timeOnSub = 0;
      String rteID = sub.getRoute().getID();
      boolean dbg = false; //curLimit_ == 2 && rNode.getID().equals("s_5P") && (rteID.equals("110") || rteID.equals("NS") || rteID.equals("NES"));
      if (dbg) {
        System.out.println(" Processing sub: " + sub.getFullID());
      }
      int rli = sub.getRouteLinkIndex(link.getEndDLI());
      List<RLink> parents = new LinkedList<RLink>();
      parents.add(link); // add first link, possibly an alight link
      for (int i = rli; i >= 0; i--) {
        RLink subLink = sub.getRouteLink(i);
        if (i < rli) {
          parents.add(subLink);
        }
        timeOnSub += (i < rli) ? subLink.timeCostBW(time - timeOnSub, service_, walkSpeedFPS_, 0) : link.timeCostBW(time - timeOnSub, service_, walkSpeedFPS_, 0);
        if (dbg) {
          System.out.println("  subLink: " + subLink.getID() + " timeOnSub: " + FPUtil.elapsedTimeStr(timeOnSub));
        }
        RNode node = rteNet_.fromNode(subLink);
        int newTime = time - timeOnSub - 60;
        //if(newTime<0) System.out.println("newTime negative!!");
        if (timeOnSub > 0 && newTime > 0 && newTime < 86400) {
          if (reachableSets_[curLimit_].contains(node) && newTime > nodeTimes_[curLimit_].get(node).intValue()) {
            /*if(curLimit_<=2 && node.getID().equals("s_5P")) {
            System.out.println("replacing time @ 5p old="+CUtil.dtime(nodeTimes_[curLimit_].get(node).intValue()));
            System.out.println(" - time="+CUtil.dtime(time));
            System.out.println(" - timeOnSub="+timeOnSub);
            }*/
            reachableSets_[curLimit_].remove(node);
          }
          if (reachableSets_[curLimit_].add(node)) {
            List<RLink> pCopy = new LinkedList<RLink>();
            pCopy.addAll(parents);
            try {
              //if(curLimit_<=2 && node.getID().equals("s_5P")) System.out.println("new nodetime @ "+node.getID()+" = "+CUtil.dtime(newTime));
              nodeTimes_[curLimit_].put(node, new Integer(time - timeOnSub - 60));
              parents_[curLimit_].put(node, pCopy);
            } catch (Exception e) {
              e.printStackTrace();
              return;
            }
            if (node == origin_) {
              foundPotential(parents, null, time - timeOnSub);
            }
          }
          if (finalLinks_.containsKey(node)) {
            Iterator<RLink> flinks = finalLinks_.get(node).iterator();
            while (flinks.hasNext()) {
              RLink fLink = flinks.next();
              if (fLink.getSubRoute().getFullID().equals(sub.getFullID())) {
                int timeCost = fLink.timeCostBW(time - timeOnSub, service_, walkSpeedFPS_, 0);
                if (dbg) {
                  System.out.println("   found potential, tos=" + timeOnSub + " tc=" + timeCost);
                }
                foundPotential(parents, fLink, time - timeOnSub - timeCost);
              }
            }
          }
        }
      }
    }
  }

  public void foundPotential(List<RLink> parents, RLink firstLink, int startTime) {
    try {
      List<RLink> pathLinks = new LinkedList<RLink>();

      Iterator<RLink> pIter = parents.iterator();
      while (pIter.hasNext()) {
        pathLinks.add(0, pIter.next());
      }
      if (firstLink != null) {
        pathLinks.add(0, firstLink);
      }
      for (int l = curLimit_ - 1; l >= 1; l--) {
        List<RLink> pLinks = parents_[l].get(rteNet_.toNode(pathLinks.get(pathLinks.size() - 1)));
        if (pLinks != null) {
          ListIterator<RLink> plIter = pLinks.listIterator(pLinks.size());
          while (plIter.hasPrevious()) {
            pathLinks.add(plIter.previous());
          }
        }
      }
      potentials_.add(pathLinks);
      //System.out.println("   added potential, startTime="+CUtil.dtime(startTime));
      //System.out.println("startTimes: "+startTimes_);
      startTimes_.add(new Integer(startTime - 90));
    //System.out.println(" added start time "+CUtil.sTimeToStr(startTime));

    } catch (Exception e) {
      e.printStackTrace();
      return;
    }
  }
}
